/*
 * To change this template, choose Tools | Templates
 * and open the template in the editor.
 */
package tpcomp2010.estructura;

import java.util.ArrayList;
import java.util.HashMap;
import java.util.List;
import java.util.Map;
import java.util.Set;

/**
 *
 * @author Victor
 */
public class Minimizacion {

    /**
     * Automana sobre el cual se realiza la minimizacion
     */
    Automata afMin;

    /**
     * Class Constructor estableciendo el automata sobre el cual se va operar
     * @param afMin
     */
    public Minimizacion(Automata afMin) {
        this.afMin = afMin;
    }

    /**
     * Algoritmo de minimizacion, realiza la minimizacion y devuelve el automata
     * minimizado
     * @return automata minimizado
     */
    public Automata minimizar() {

        /*Crear 1ra agrupacion PI inicial
         *  PIinicial = { ListaNodosFinales, ListaNodosNoFinales }
         */
        ListaNodos listaFinales = afMin.getNodosFinales();
        ListaNodos listaNoFinales = afMin.getNoFinales();

        ArrayList<ListaNodos> PI = new ArrayList<ListaNodos>();

        ArrayList<ListaNodos> PInueva = new ArrayList<ListaNodos>();
        ArrayList<ListaNodos> PIfinal = new ArrayList<ListaNodos>();

        PI.add(listaFinales);
        PI.add(listaNoFinales);

        PInueva = (ArrayList<ListaNodos>) PI.clone();

        //List<Map<String, ListaNodos>> gruposNuevos = new ArrayList<Map<String, ListaNodos>>();

        boolean seguir = true;

        while (seguir) {
            PInueva = dividir(PI);
            if (!compararPIS(PI, PInueva)) {
                PI = (ArrayList<ListaNodos>) PInueva.clone();
            } else {
                seguir = false;
            }
            //gruposNuevos = new ArrayList<Map<String, ListaNodos>>();
        }
        System.out.println("");
        try {
            //crear el automata AFD Minimo
            return crearAutomata(PInueva);
        } catch (Exception ex) {
            return null;
        }


    }

    /**
     * Crea un automata a partir de un array de lista de nodos
     * @param PI array de lista de nodos
     * @return el automata que resulta de los nodos contenidos en PI
     * @throws Exception
     */
    private Automata crearAutomata(ArrayList<ListaNodos> PI) throws Exception {
        Automata AFDMin = new Automata();

        for (ListaNodos lest : PI) {
            Nodo nuevo = new Nodo(lest.getId(), false, false, false);

            //Es estado inicial
            try {
                lest.getNodoInicial();
                nuevo.setNodoinicial(true);
                AFDMin.setInicial(nuevo);
            } catch (Exception ex) {
                nuevo.setNodoinicial(false);
            }

            //Es estado final
            if (lest.getNodoFinales().cantidad() > 0) {
                nuevo.setNodofinal(true);
                AFDMin.getNodosFinales().insertar(nuevo);
            } else {
                nuevo.setNodofinal(false);
            }
            AFDMin.addNodo(nuevo);
        }

        for (ListaNodos listNodoActual : PI) {

            Nodo nodoAFDMin = AFDMin.getNodoById(listNodoActual.getId());
            Nodo representante = listNodoActual.get(0);

            for (Arista ari : representante.getAristas()) {
                ListaNodos listaDestino = getListaPertenece(PI, ari.getNodoDestino());
                Nodo nodoDestino = AFDMin.getNodoById(listaDestino.getId());
                Arista nuevaArista = new Arista(nodoAFDMin, nodoDestino, ari.getEtiqueta());
                nodoAFDMin.agregarArista(nuevaArista);
            }
        }
        return AFDMin;
    }

    /**
     * Dada un array de ListaNodo, determina a cual de las ListaNodo pertenece
     * un nodo dado
     * @param listas array de lista nodos
     * @param estado el nodo a buscar
     * @return La lista a la cual perteneceel nodo, null en caso de que no
     * pertenezca a ninguna
     */
    public ListaNodos getListaPertenece(ArrayList<ListaNodos> listas, Nodo estado) {
        for (ListaNodos lista : listas) {
            try {
                lista.getNodoById(estado.getId());
                return lista;
            } catch (Exception ex) {
            }
        }
        return null;
    }

    /**
     * Dada un array de ListaNodos realiza la division de los grupos, segun se especifica
     * en el algoritmo de minimizacion
     * @param PI lista a dividir
     * @return un nuevo array de ListaNodos ya divididos.
     */
    private ArrayList<ListaNodos> dividir(ArrayList<ListaNodos> PI) {
        List<Map<String, ListaNodos>> gruposNuevos = new ArrayList<Map<String, ListaNodos>>();
        ArrayList<ListaNodos> PINuevo = null;

        int j = 0;
        for (ListaNodos listaNodos : PI) {
            listaNodos.setId(j++);
        }

        for (ListaNodos listaNodosActual : PI) {
            Map<String, ListaNodos> hash = new HashMap<String, ListaNodos>();
            Nodo[] lista = listaNodosActual.toArray(new Nodo[0]);

            for (int i = 0; i < lista.length; i++) {
                Nodo nodo = lista[i];
                String claveHash = new String();
                for (String letra : afMin.getAlfabeto()) {

                    Nodo destino = nodo.getDestino(letra);
                    claveHash += getIdGrupo(PI, destino);

                }
                if (hash.get(claveHash) == null) {
                    hash.put(claveHash, new ListaNodos());
                }
                hash.get(claveHash).insertar(nodo);
            }
            gruposNuevos.add(hash);
        }
        PINuevo = new ArrayList<ListaNodos>();
        int i = 0;
        for (Map<String, ListaNodos> mapa : gruposNuevos) {
            Set<String> claves = mapa.keySet();
            for (String clave : claves) {
                ListaNodos ln = mapa.get(clave);
                ln.setId(i++);
                PINuevo.add(ln);
            }
        }
        return PINuevo;
    }

    /**
     * Compara dos arrays de ListaNodos
     * @param PI1 primera lista para comparar
     * @param PI2 segunda lista para comparar con la primera
     * @return true si son iguales, false en caso contrario
     */
    private boolean compararPIS(ArrayList<ListaNodos> PI1, ArrayList<ListaNodos> PI2) {
        if (PI1.size() != PI2.size()) {
            return false;
        }
        int cantidad = 0;
        for (ListaNodos lnPI1 : PI1) {
            for (ListaNodos lnPI2 : PI2) {
                if (lnPI1.equals(lnPI2)) {
                    cantidad++;
                    break;
                }
            }
        }
        if (cantidad == PI1.size()) {
            return true;
        }

        return false;
    }

    /**
     * Develve el ID de la ListaNodo al que pertenece el nodo dado
     * @param pi lista donde se busca el nodo
     * @param destino nodo que se busca en las listas
     * @return el id del grupo, o listaNodo, al cual pertenece, -1 en caso de
     * que no pertenezca a ninguno.
     */
    private int getIdGrupo(List<ListaNodos> pi, Nodo destino) {
        for (ListaNodos lista : pi) {
            if (lista.contiene(destino)) {
                return lista.getId();
            }
        }
        return -1;
    }
}


